class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 4:
            return n
        f0 ,f1 = 1,2

        for i in range(2,n):
            f0,f1 = f1,f1+f0
        
        return f1

class Solution:
    def climbStairs(self, n: int) -> int:
        cache = [-1] * (n+1)
        def dfs(i):
            if i < 4:
                return i
            if cache[i] != -1:
                return cache[i]
            res = dfs(i-1) + dfs(i-2)
            cache[i] = res
            return res
        return dfs(n)
            
class Solution:
    def climbStairs(self, n: int) -> int:
        f = [0] * (n+1)
        for i in range(1,n+1):
            if i < 4:
                f[i] = i
            else:
                f[i] = f[i-1] + f[i-2]

        return f[-1]
            
